public class Main {
    static class NodeList {
        private NodeList next;
        private  int val;

        public NodeList(int val) {
            this.val = val;
        }
    }
    public NodeList head;

    public void clear() {
        if(head == null ){
            return;
        }
        NodeList node = this.head;
        NodeList cur = this.head.next;

        while(cur != null) {
            head.next = null;
            head = cur;
            cur = cur.next;
        }
        this.head = null;
    }
    //删除指定的所有节点
    public void removeAll(int key) {
        if(head == null) {
            return;
        }
        NodeList node = this.head;
        NodeList cur = this.head.next;

        while(cur != null) {
            if(cur.val == key) {
                node.next = cur.next;
                cur = cur.next;
            }else {
                node = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key) {
            head = head.next;
        }
    }
    public void Display() {
        NodeList node = this.head;

        while(node != null) {
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println();
    }
    public void Display(NodeList Nexthead) {
        NodeList node = Nexthead;

        while(node != null) {
            System.out.print(node.val+" ");
            node = node.next;
        }
        System.out.println();
    }

    //头插法
    public void addFirst(int data) {
        NodeList node = new NodeList(data);
        node.next = head;
        head = node;
    }

    public boolean chkPalindrome(NodeList head) {
        NodeList fast = head;
        NodeList slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        NodeList cur = slow.next;
        while(cur != null) {
            NodeList curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }

        while(head != slow) {
            if(head.val != slow.val){
                return false;
            }
            if(head.next == slow ) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    public NodeList mergeTwoLists(NodeList list1, NodeList list2) {

        if(list1 == null ) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }
        NodeList newhead = new NodeList(5);
        NodeList cur = newhead;

        while(list1 != null && list2 != null) {
            if(list1.val < list2.val ) {
                cur.next = list1;
                list1 = list1.next;
                cur = cur.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
                cur = cur.next;
            }
        }
        if(list1 != null) {
            cur.next = list1;
        }

        if(list2 != null) {
            cur.next = list2;
        }

        return newhead.next;
    }
    public NodeList partition(int x) {
        NodeList a1= null;
        NodeList a2 = null;
        NodeList b1= null;
        NodeList b2 = null;

        NodeList cur = head;
        while(cur != null) {
            if(cur.val < x) {
                if(a1 == null) {
                    a1 = cur;//判断是否是首次插入
                    a2 = cur;
                } else {
                    a2.next = cur;
                    a2 = a2.next;
                }
            }else {
                if(b1 == null) {
                    b1 = cur;
                    b2 = cur;
                }else {
                    b2.next = cur;
                    b2 = b2.next;
                }
            }
            cur = cur.next;
        }

        if(a1 == null) {
            return b1;
        }
        a2.next = b1;

        if(b1 != null) {
            b2.next = null;
        }
        return a1;
    }
}
